/**
  @(#)$Id: AL_TreeNodeBinList.h 85 2013-10-17 11:37:59Z xiaoting $
  @brief	Each of the data structure corresponds to a data node storage unit, this storage unit is called storage node, the node can 
  also be referred to.
	
  The related concepts of tree node 
  1.degree		degree node: A node of the subtree containing the number is called the node degree;
  2.leaf			leaf nodes or terminal nodes: degree 0 are called leaf nodes;
  3.branch		non-terminal node or branch node: node degree is not 0;
  4.parent		parent node or the parent node: If a node contains a child node, this node is called its child node's parent;
  5.child			child node or child node: A node subtree containing the root node is called the node's children;
  6.slibing		sibling nodes: nodes with the same parent node is called mutual sibling;
  7.ancestor		ancestor node: from the root to the node through all the nodes on the branch;
  8.descendant	descendant nodes: a node in the subtree rooted at any node is called the node's descendants.

  ////////////////////////////////Binary Tree//////////////////////////////////////////
  In computer science, a binary tree is that each node has at most two sub-trees ordered tree. Usually the root of the subtree is 
  called "left subtree" (left subtree) and the "right subtree" (right subtree). Binary tree is often used as a binary search tree 
  and binary heap or a binary sort tree. Binary tree each node has at most two sub-tree (does not exist a degree greater than two 
  nodes), left and right sub-tree binary tree of the points, the order can not be reversed. Binary i-th layer of at most 2 power 
  nodes i -1; binary tree of depth k at most 2 ^ (k) -1 nodes; for any binary tree T, if it is the terminal nodes (i.e. leaf nodes) 
  is, the nodes of degree 2 is, then = + 1.

  ////////////////////////////////Chain storage structure//////////////////////////////////////////
  The computer using a set of arbitrary linear table storage unit stores data elements (which may be a continuous plurality of memory 
  cells, it can be discontinuous).

  It does not require the logic elements of adjacent physical location is adjacent to and therefore it is not sequential storage 
  structure has a weakness, but also lost the sequence table can be accessed randomly advantages.

  Chain store structural features:
  1, compared with sequential storage density storage structure (each node consists of data fields and pointers domains, so the same 
  space is full, then assume full order of more than chain stores).
  2, the logic is not required on the adjacent node is physically adjacent.
  3, insert, delete and flexible (not the mobile node, change the node as long as the pointer).
  4, find the node when stored sequentially slower than the chain stores.
  5, each node is a pointer to the data fields and domains.

  @Author $Author: xiaoting $
  @Date $Date: 2013-10-17 19:37:59 +0800 (周四, 17 十月 2013) $
  @Revision $Revision: 85 $
  @URL $URL: https://svn.code.sf.net/p/xiaoting/game/trunk/MyProject/AL_DataStructure/groupinc/AL_TreeNodeBinList.h $
  @Header $Header: https://svn.code.sf.net/p/xiaoting/game/trunk/MyProject/AL_DataStructure/groupinc/AL_TreeNodeBinList.h 85 2013-10-17 11:37:59Z xiaoting $
 */

#ifndef CXX_AL_TREENODEBINLIST_H
#define CXX_AL_TREENODEBINLIST_H

#ifndef CXX_AL_LISTSINGLE_H
#include "AL_ListSingle.h"
#endif

#ifndef CXX_AL_QUEUELIST_H
#include "AL_QueueList.h"
#endif


///////////////////////////////////////////////////////////////////////////
//			AL_TreeNodeBinList
///////////////////////////////////////////////////////////////////////////

template<typename T> class AL_TreeBinList;
template<typename T> class AL_TreeHuffmanList;

template<typename T> 
class AL_TreeNodeBinList
{
friend class AL_TreeBinList<T>;
friend class AL_TreeHuffmanList<T>;
template<typename T, typename Compare> friend class AL_QueuePriorityList;

public:
	/**
	* Destruction
	*
	* @param
	* @return
	* @note
	* @attention 
	*/
	~AL_TreeNodeBinList();
	
	/**
	* GetLevel
	*
	* @param
	* @return	DWORD
	* @note Node levels: starting from the root to start defining the root of the first layer, the root node is a sub-layer 2, and so on;	
	* @attention 
	*/
	DWORD GetLevel() const;

	/**
	* SetLevel
	*
	* @param	DWORD dwLevel <IN>
	* @return	
	* @note Node levels: starting from the root to start defining the root of the first layer, the root node is a sub-layer 2, and so on;	
	* @attention 
	*/
	VOID SetLevel(DWORD dwLevel);

	/**
	* GetWeight
	*
	* @param
	* @return	DWORD
	* @note If the tree node is assigned a numerical value has some meaning, then this value is called the node weights
	* @attention only be used in Huffman tree...
	*/
	DWORD GetWeight() const;

	/**
	* SetWeight
	*
	* @param	DWORD dwWeight <IN>
	* @return	
	* @note If the tree node is assigned a numerical value has some meaning, then this value is called the node weights
	* @attention only be used in Huffman tree...
	*/
	VOID SetWeight(DWORD dwWeight);

	/**
	* GetData
	*
	* @param
	* @return	T
	* @note 
	* @attention 
	*/
	T GetData() const;

	/**
	* SetData
	*
	* @param	const T& tData <IN>
	* @return	
	* @note 
	* @attention 
	*/
	VOID SetData(const T& tData);

	/**
	* GetParent
	*
	* @param	
	* @return	AL_TreeNodeBinList<T>*	
	* @note parent node pointer, not to manager memory
	* @attention 
	*/
	AL_TreeNodeBinList<T>*	GetParent() const;

	/**
	* SetParent
	*
	* @param	DWORD dwIndex <IN>
	* @param	AL_TreeNodeBinList<T>* pParent <IN>
	* @return	BOOL
	* @note parent node pointer, not to manager memory
	* @attention as the child to set the parent at the index (from the left of parent's child ) [0x00: left child, 0x01: right child]
	*/
	BOOL SetParent(DWORD dwIndex, AL_TreeNodeBinList<T>* pParent);

	/**
	* SetParentLeft
	*
	* @param	AL_TreeNodeBinList<T>* pParent <IN>
	* @return	BOOL
	* @note parent node pointer, not to manager memory
	* @attention as the child to set the parent at the left (from the left of parent's child )
	*/
	BOOL SetParentLeft(AL_TreeNodeBinList<T>* pParent);

	/**
	* SetParentRight
	*
	* @param	AL_TreeNodeBinList<T>* pParent <IN>
	* @return	BOOL
	* @note parent node pointer, not to manager memory
	* @attention as the child to set the parent at the right (from the right of parent's child )
	*/
	BOOL SetParentRight(AL_TreeNodeBinList<T>* pParent);

	/**
	* Insert
	*
	* @param	DWORD dwIndex <IN>
	* @param	AL_TreeNodeBinList<T>* pInsertChild <IN> 
	* @return	BOOL
	* @note inset the const AL_TreeNodeBinList<T>*  into the child notes at the position [0x00: left child, 0x01: right child]
	* @attention
	*/
	BOOL Insert(DWORD dwIndex, AL_TreeNodeBinList<T>* pInsertChild);

	/**
	* InsertLeft
	*
	* @param	AL_TreeNodeBinList<T>* pInsertChild <IN> 
	* @return	BOOL
	* @note inset the const AL_TreeNodeBinList<T>*  into the child notes at the left
	* @attention
	*/
	BOOL InsertLeft(AL_TreeNodeBinList<T>* pInsertChild);

	/**
	* InsertRight
	*
	* @param	AL_TreeNodeBinList<T>* pInsertChild <IN> 
	* @return	BOOL
	* @note inset the const AL_TreeNodeBinList<T>*  into the child notes at the right
	* @attention
	*/
	BOOL InsertRight(AL_TreeNodeBinList<T>* pInsertChild);

	/**
	* RemoveParent
	*
	* @param
	* @return	BOOL
	* @note remove the parent note
	* @attention
	*/
	BOOL RemoveParent();
	
	/**
	* Remove
	*
	* @param	AL_TreeNodeBinList<T>* pRemoveChild <IN>
	* @return	BOOL
	* @note remove the notes in the child
	* @attention
	*/
	BOOL Remove(AL_TreeNodeBinList<T>* pRemoveChild);

	/**
	* Remove
	*
	* @param	DWORD dwIndex <IN>
	* @return	BOOL
	* @note remove the child notes at the position [0x00: left child, 0x01: right child]
	* @attention
	*/
	BOOL Remove(DWORD dwIndex);

	/**
	* RemoveLeft
	*
	* @param
	* @return	BOOL
	* @note remove the child notes at the left
	* @attention
	*/
	BOOL RemoveLeft();

	/**
	* RemoveRight
	*
	* @param
	* @return	BOOL
	* @note remove the child notes at the right
	* @attention
	*/
	BOOL RemoveRight();

	/**
	* GetChildLeft
	*
	* @param	
	* @return	AL_TreeNodeBinList<T>*
	* @note 
	* @attention
	*/
	AL_TreeNodeBinList<T>* GetChildLeft() const;

	/**
	* GetChildRight
	*
	* @param	
	* @return	AL_TreeNodeBinList<T>*
	* @note 
	* @attention
	*/
	AL_TreeNodeBinList<T>* GetChildRight() const;
	
	/**
	* GetDegree
	*
	* @param
	* @return	DWORD
	* @note degree node: A node of the subtree containing the number is called the node degree;
	* @attention 
	*/
	DWORD GetDegree() const;

	/**
	* IsLeaf
	*
	* @param
	* @return	BOOL
	* @note leaf nodes or terminal nodes: degree 0 are called leaf nodes;
	* @attention 
	*/
	BOOL IsLeaf() const;

	/**
	* IsBranch
	*
	* @param
	* @return	BOOL
	* @note non-terminal node or branch node: node degree is not 0;
	* @attention 
	*/
	BOOL IsBranch() const;

	/**
	* IsParent
	*
	* @param	const AL_TreeNodeBinList<T>* pChild <IN>
	* @return	BOOL
	* @note parent node or the parent node: If a node contains a child node, this node is called its child 
	* @attention 
	*/
	BOOL IsParent(const AL_TreeNodeBinList<T>* pChild) const;

	/**
	* GetSibling
	*
	* @param	AL_ListSingle<AL_TreeNodeBinList<T>*>& listSibling <OUT>
	* @return	BOOL
	* @note sibling nodes: nodes with the same parent node is called mutual sibling;
	* @attention 
	*/
	BOOL GetSibling(AL_ListSingle<AL_TreeNodeBinList<T>*>& listSibling) const;

	/**
	* GetAncestor
	*
	* @param	AL_ListSingle<AL_TreeNodeBinList<T>*>& listAncestor <OUT>
	* @return	BOOL
	* @note ancestor node: from the root to the node through all the nodes on the branch;
	* @attention 
	*/
	BOOL GetAncestor(AL_ListSingle<AL_TreeNodeBinList<T>*>& listAncestor) const;

	/**
	* GetDescendant
	*
	* @param	AL_ListSingle<AL_TreeNodeBinList<T>*>& listDescendant <OUT>
	* @return	BOOL
	* @note ancestor node: from the root to the node through all the nodes on the branch;
	* @attention 
	*/
	BOOL GetDescendant(AL_ListSingle<AL_TreeNodeBinList<T>*>& listDescendant) const;

	/**
	* Clear
	*
	* @param
	* @return	VOID
	* @note
	* @attention 
	*/
	VOID Clear();

	/**
	* operator () 
	*
	* @param	const AL_TreeNodeBinList<T>& _Left <IN>
	* @param	const AL_TreeNodeBinList<T>& _Right <IN>
	* @return	BOOL
	* @note		Overload "()" operator, allowing the use of this class like a function. We put such a class is called a function object, 
				or called pseudo function, a function can be used as examples.
    	Advantages: 
				Using the functor just like using a normal function the same, but its realization functor can access all the member 
				variables for access; rather ordinary function to communicate can only rely on global variables.
	* @attention 
	*/
	BOOL operator () (const AL_TreeNodeBinList<T>& _Left, const AL_TreeNodeBinList<T>& _Right) const;

	/**
	* operator () 
	*
	* @param	const AL_TreeNodeBinList<T>* _Left <IN>
	* @param	const AL_TreeNodeBinList<T>* _Right <IN>
	* @return	BOOL
	* @note		Overload "()" operator, allowing the use of this class like a function. We put such a class is called a function object, 
				or called pseudo function, a function can be used as examples.
    	Advantages: 
				Using the functor just like using a normal function the same, but its realization functor can access all the member 
				variables for access; rather ordinary function to communicate can only rely on global variables.
		* @attention 
	*/
	BOOL operator () (const AL_TreeNodeBinList<T>* _Left, const AL_TreeNodeBinList<T>* _Right) const;

protected:
private:

	/**
	* Construction
	*
	* @param
	* @return
	* @note private the Construction, avoid the others use it
	* @attention
	*/
	AL_TreeNodeBinList();
	
	/**
	* Construction
	*
	* @param	const T& tData <IN>
	* @return
	* @note
	* @attention private the Construction, avoid the others use it
	*/
	AL_TreeNodeBinList(const T& tData);

	/**
	*Copy Construct
	*
	* @param	const AL_TreeNodeBinList<T>& cAL_TreeNodeBinList
	* @return
	*/
	AL_TreeNodeBinList(const AL_TreeNodeBinList<T>& cAL_TreeNodeBinList);

	/**
	*Assignment
	*
	* @param	const AL_TreeNodeBinList<T>& cAL_TreeNodeBinList
	* @return	AL_TreeNodeBinList<T>&
	*/
	AL_TreeNodeBinList<T>& operator = (const AL_TreeNodeBinList<T>& cAL_TreeNodeBinList);

public:
protected:
private:
	DWORD								m_dwLevel;				//Node levels: starting from the root to start defining the root of the first layer, the root node is a sub-layer 2, and so on;	
	DWORD								m_dwWeight;				//If the tree node is assigned a numerical value has some meaning, then this value is called the node weights
																//only be used in Huffman tree...
	
	T									m_tData;					//the friend class can use it directly

	AL_TreeNodeBinList<T>*				m_pParent;				//Parent position
	AL_TreeNodeBinList<T>*				m_pChildLeft;			//Child tree node left
	AL_TreeNodeBinList<T>*				m_pChildRight;			//Child tree node right
};

///////////////////////////////////////////////////////////////////////////
//			AL_TreeNodeBinList
///////////////////////////////////////////////////////////////////////////

/**
* Construction
*
* @param
* @return
* @note private the Construction, avoid the others use it
* @attention
*/
template<typename T>
AL_TreeNodeBinList<T>::AL_TreeNodeBinList():
m_dwLevel(0x00),
m_dwWeight(0x00),
m_pParent(NULL),
m_pChildLeft(NULL),
m_pChildRight(NULL)
{

}

/**
* Construction
*
* @param	const T& tData <IN>
* @return
* @note
* @attention private the Construction, avoid the others use it
*/
template<typename T>
AL_TreeNodeBinList<T>::AL_TreeNodeBinList(const T& tData):
m_dwLevel(0x00),
m_tData(tData),
m_pParent(NULL),
m_pChildLeft(NULL),
m_pChildRight(NULL)
{

}


/**
* Destruction
*
* @param
* @return
* @note
* @attention 
*/
template<typename T>
AL_TreeNodeBinList<T>::~AL_TreeNodeBinList()
{
	//it doesn't matter to clear the pointer or not.
	Clear();
}

/**
* GetLevel
*
* @param
* @return	DWORD
* @note Node levels: starting from the root to start defining the root of the first layer, the root node is a sub-layer 2, and so on;	
* @attention 
*/
template<typename T> DWORD 
AL_TreeNodeBinList<T>::GetLevel() const
{
	return m_dwLevel;
}

/**
* SetLevel
*
* @param	DWORD dwLevel <IN>
* @return	
* @note Node levels: starting from the root to start defining the root of the first layer, the root node is a sub-layer 2, and so on;	
* @attention 
*/
template<typename T> VOID 
AL_TreeNodeBinList<T>::SetLevel(DWORD dwLevel)
{
	m_dwLevel = dwLevel;
}

/**
* GetWeight
*
* @param
* @return	DWORD
* @note If the tree node is assigned a numerical value has some meaning, then this value is called the node weights
* @attention only be used in Huffman tree...
*/
template<typename T> DWORD 
AL_TreeNodeBinList<T>::GetWeight() const
{
	return m_dwWeight;
}

/**
* SetWeight
*
* @param	DWORD dwWeight <IN>
* @return	
* @note If the tree node is assigned a numerical value has some meaning, then this value is called the node weights
* @attention only be used in Huffman tree...
*/
template<typename T> VOID 
AL_TreeNodeBinList<T>::SetWeight(DWORD dwWeight)
{
	m_dwWeight = dwWeight;
}

/**
* GetData
*
* @param
* @return	T
* @note 
* @attention 
*/
template<typename T> T 
AL_TreeNodeBinList<T>::GetData() const
{
	return m_tData;
}

/**
* SetData
*
* @param	const T& tData <IN>
* @return	
* @note 
* @attention 
*/
template<typename T> VOID 
AL_TreeNodeBinList<T>::SetData(const T& tData)
{
	m_tData = tData;
}

/**
* GetParent
*
* @param	
* @return	AL_TreeNodeBinList<T>*	
* @note parent node pointer, not to manager memory
* @attention 
*/
template<typename T> AL_TreeNodeBinList<T>* 
AL_TreeNodeBinList<T>::GetParent() const
{
	return m_pParent;
}

/**
* SetParent
*
* @param	DWORD dwIndex <IN>
* @param	AL_TreeNodeBinList<T>* pParent <IN>
* @return	BOOL
* @note parent node pointer, not to manager memory
* @attention as the child to set the parent at the index (from the left of parent's child ) [0x00: left child, 0x01: right child]
*/
template<typename T> BOOL 
AL_TreeNodeBinList<T>::SetParent(DWORD dwIndex, AL_TreeNodeBinList<T>* pParent)
{
	if (NULL == pParent) {
		return FALSE;
	}

	BOOL  bSetParent = FALSE;
	bSetParent = pParent->Insert(dwIndex, this);
	if (TRUE == bSetParent) {
		//current node insert to the parent successfully
		if (NULL != m_pParent) {
			//current node has parent
			if (FALSE == m_pParent->Remove(this)) {
				return FALSE;
			}
		}
		m_pParent = pParent;
	}
	return bSetParent;
}

/**
* SetParentLeft
*
* @param	AL_TreeNodeBinList<T>* pParent <IN>
* @return	
* @note parent node pointer, not to manager memory
* @attention as the child to set the parent at the left (from the left of parent's child )
*/
template<typename T> BOOL 
AL_TreeNodeBinList<T>::SetParentLeft(AL_TreeNodeBinList<T>* pParent)
{
	return SetParent(0x00, pParent);
}

/**
* SetParentRight
*
* @param	AL_TreeNodeBinList<T>* pParent <IN>
* @return	
* @note parent node pointer, not to manager memory
* @attention as the child to set the parent at the right (from the right of parent's child )
*/
template<typename T> BOOL 
AL_TreeNodeBinList<T>::SetParentRight(AL_TreeNodeBinList<T>* pParent)
{
	return SetParent(0x01, pParent);
}

/**
* Insert
*
* @param	DWORD dwIndex <IN>
* @param	AL_TreeNodeBinList<T>* pInsertChild <IN> 
* @return	BOOL
* @note inset the const AL_TreeNodeBinList<T>*  into the child notes at the position [0x00: left child, 0x01: right child]
* @attention
*/
template<typename T> BOOL 
AL_TreeNodeBinList<T>::Insert(DWORD dwIndex, AL_TreeNodeBinList<T>* pInsertChild)
{
	if (0x01 < dwIndex || NULL == pInsertChild) {
		return FALSE;
	}
	
	if (this == pInsertChild) {
		//itself
		return FALSE;
	}

	BOOL  bInsert = FALSE;
	if (0x00 == dwIndex && NULL == m_pChildLeft) {
		//left and the child left not exist
		m_pChildLeft = pInsertChild;
		bInsert = TRUE;
	}
	else if (0x01 == dwIndex && NULL == m_pChildRight) {
		//right and the child right not exist
		m_pChildRight = pInsertChild;
		bInsert = TRUE;
	}
	else {
		//no case
		bInsert = FALSE;
	}

	if (TRUE == bInsert) {
		if (GetLevel()+1 != pInsertChild->GetLevel()) {
			//deal with the child level
			INT iLevelDiff = pInsertChild->GetLevel() - GetLevel();
			pInsertChild->SetLevel(GetLevel()+1);

			AL_ListSingle<AL_TreeNodeBinList<T>*> listDescendant;
			if (TRUE == pInsertChild->GetDescendant(listDescendant)) {
				//insert child node has descendant
				AL_TreeNodeBinList<T>* pDescendant = NULL;
				for (DWORD dwCnt=0x00; dwCnt<listDescendant.Length(); dwCnt++) {
					if (TRUE == listDescendant.Get(dwCnt, pDescendant)) {
						if (NULL != pDescendant) {
							//set child level
							pDescendant->SetLevel(pDescendant->GetLevel()-iLevelDiff+1);
						}
						else {
							//error
							return FALSE;
						}
					}
					else {
						//error
						return FALSE;
					}
				}
			}
		}
		//child node insert to the current successfully
		pInsertChild->m_pParent = this;
	}
	return bInsert;
}

/**
* InsertLeft
*
* @param	AL_TreeNodeBinList<T>* pInsertChild <IN> 
* @return	BOOL
* @note inset the const AL_TreeNodeBinList<T>*  into the child notes at the left
* @attention
*/
template<typename T> BOOL 
AL_TreeNodeBinList<T>::InsertLeft(AL_TreeNodeBinList<T>* pInsertChild)
{
	return Insert(0x00, pInsertChild);
}

/**
* InsertRight
*
* @param	AL_TreeNodeBinList<T>* pInsertChild <IN> 
* @return	BOOL
* @note inset the const AL_TreeNodeBinList<T>*  into the child notes at the right
* @attention
*/
template<typename T> BOOL 
AL_TreeNodeBinList<T>::InsertRight(AL_TreeNodeBinList<T>* pInsertChild)
{
	return Insert(0x01, pInsertChild);
}

/**
* RemoveParent
*
* @param
* @return	BOOL
* @note remove the parent note
* @attention
*/
template<typename T> BOOL 
AL_TreeNodeBinList<T>::RemoveParent()
{
	BOOL bRemove = FALSE;
	//don't care the parent node exist or not
	m_pParent = NULL;
	bRemove = TRUE;
	/*
	if (NULL != m_pParent) {
		m_pParent = NULL;
		bRemove = TRUE;
	}
	*/
	return bRemove;
}

/**
* Remove
*
* @param	AL_TreeNodeBinList<T>* pRemoveChild <IN>
* @return	BOOL
* @note remove the notes in the child
* @attention
*/
template<typename T> BOOL 
AL_TreeNodeBinList<T>::Remove(AL_TreeNodeBinList<T>* pRemoveChild)
{
	BOOL bRemove = FALSE;
	if (m_pChildLeft == pRemoveChild) {
		m_pChildLeft = NULL;
		bRemove = TRUE;
	}
	else if (m_pChildRight ==  pRemoveChild) {
		m_pChildRight = NULL;
		bRemove = TRUE;
	}
	else {
		bRemove = FALSE;
	}
	return bRemove;
}

/**
* Remove
*
* @param	DWORD dwIndex <IN>
* @return	BOOL
* @note remove the child notes at the position [0x00: left child, 0x01: right child]
* @attention
*/
template<typename T> BOOL 
AL_TreeNodeBinList<T>::Remove(DWORD dwIndex)
{
	AL_TreeNodeBinList<T>* pRemoveChild = NULL;
	if (0x00 == dwIndex) {
		pRemoveChild = m_pChildLeft;
	}
	else if (0x01 == dwIndex) {
		pRemoveChild = m_pChildRight;
	}
	else {
		return FALSE;
	}

	return Remove(pRemoveChild);
}

/**
* RemoveLeft
*
* @param
* @return	BOOL
* @note remove the child notes at the left
* @attention
*/
template<typename T> BOOL 
AL_TreeNodeBinList<T>::RemoveLeft()
{
	return Remove(m_pChildLeft);
}

/**
* RemoveRight
*
* @param
* @return	BOOL
* @note remove the child notes at the right
* @attention
*/
template<typename T> BOOL 
AL_TreeNodeBinList<T>::RemoveRight()
{
	return Remove(m_pChildRight);
}

/**
* GetChildLeft
*
* @param	
* @return	AL_TreeNodeBinList<T>*
* @note 
* @attention
*/
template<typename T> AL_TreeNodeBinList<T>* 
AL_TreeNodeBinList<T>::GetChildLeft() const
{
	return m_pChildLeft;
}

/**
* GetChildRight
*
* @param	
* @return	AL_TreeNodeBinList<T>*
* @note 
* @attention
*/
template<typename T> AL_TreeNodeBinList<T>* 
AL_TreeNodeBinList<T>::GetChildRight() const
{
	return m_pChildRight;
}

/**
* GetDegree
*
* @param
* @return	DWORD
* @note degree node: A node of the subtree containing the number is called the node degree;
* @attention 
*/
template<typename T> DWORD 
AL_TreeNodeBinList<T>::GetDegree() const
{
	DWORD dwDegree = 0x00;
	if (NULL != m_pChildLeft) {
		dwDegree++;
	}
	if (NULL != m_pChildRight) {
		dwDegree++;
	}

	return dwDegree;
}

/**
* IsLeaf
*
* @param
* @return	BOOL
* @note leaf nodes or terminal nodes: degree 0 are called leaf nodes;
* @attention 
*/
template<typename T> BOOL 
AL_TreeNodeBinList<T>::IsLeaf() const
{
	return (0x00 == GetDegree()) ? TRUE:FALSE;
}

/**
* IsBranch
*
* @param
* @return	BOOL
* @note non-terminal node or branch node: node degree is not 0;
* @attention 
*/
template<typename T> BOOL 
AL_TreeNodeBinList<T>::IsBranch() const
{
	return (0x00 != GetDegree()) ? TRUE:FALSE;
}

/**
* IsParent
*
* @param	const AL_TreeNodeBinList<T>* pChild <IN>
* @return	BOOL
* @note parent node or the parent node: If a node contains a child node, this node is called its child 
* @attention 
*/
template<typename T> BOOL 
AL_TreeNodeBinList<T>::IsParent(const AL_TreeNodeBinList<T>* pChild) const
{
	if (NULL ==  pChild) {
		return FALSE;
	}
	// 	AL_TreeNodeBinList<T>* pCompare = NULL;
	// 	for (DWORD dwCnt=0x00; dwCnt<GetDegree(); dwCnt++) {
	// 		if (TRUE == m_listChild.Get(pCompare, dwCnt)) {
	// 			if (pCompare == pChild) {
	// 				//find the child
	// 				return TRUE;
	// 			}
	// 		}
	// 	}
	// 	return FALSE;

	if (this == pChild->m_pParent) {
		return TRUE;
	}
	return FALSE;
}

/**
* GetSibling
*
* @param	AL_ListSingle<AL_TreeNodeBinList<T>*>& listSibling <OUT>
* @return	BOOL
* @note sibling nodes: nodes with the same parent node is called mutual sibling;
* @attention 
*/
template<typename T> BOOL
AL_TreeNodeBinList<T>::GetSibling(AL_ListSingle<AL_TreeNodeBinList<T>*>& listSibling) const
{
	BOOL bSibling = FALSE;
	if (NULL == m_pParent) {
		//not parent node
		return bSibling;
	}

	listSibling.Clear();

	AL_TreeNodeBinList<T>* pParentChild = GetChildLeft();
	if (NULL != pParentChild) {
		if (pParentChild != this) {
			//not itself
			listSibling.InsertEnd(pParentChild);
			bSibling = TRUE;
		}
	}

	pParentChild = GetChildRight();
	if (NULL != pParentChild) {
		if (pParentChild != this) {
			//not itself
			listSibling.InsertEnd(pParentChild);
			bSibling = TRUE;
		}
	}

	return bSibling;
}

/**
* GetAncestor
*
* @param	AL_ListSingle<AL_TreeNodeBinList<T>*>& listAncestor <OUT>
* @return	BOOL
* @note ancestor node: from the root to the node through all the nodes on the branch;
* @attention 
*/
template<typename T> BOOL
AL_TreeNodeBinList<T>::GetAncestor(AL_ListSingle<AL_TreeNodeBinList<T>*>& listAncestor) const
{
	if (NULL == m_pParent) {
		//not parent node
		return FALSE;
	}

	listAncestor.Clear();
	AL_TreeNodeBinList<T>* pParent = m_pParent;
	while (NULL != pParent) {
		listAncestor.InsertEnd(pParent);
		pParent = pParent->m_pParent;
	}
	return TRUE;
}

/**
* GetDescendant
*
* @param	AL_ListSingle<AL_TreeNodeBinList<T>*>& listDescendant <OUT>
* @return	BOOL
* @note ancestor node: from the root to the node through all the nodes on the branch;
* @attention 
*/
template<typename T> BOOL 
AL_TreeNodeBinList<T>::GetDescendant(AL_ListSingle<AL_TreeNodeBinList<T>*>& listDescendant) const
{
	if (TRUE == IsLeaf()) {
		//child node
		return FALSE;
	}
	
	listDescendant.Clear();
	AL_TreeNodeBinList<T>* pDescendant = GetChildLeft();
	if (NULL != pDescendant) {
		listDescendant.InsertEnd(pDescendant);
	}

	pDescendant = GetChildRight();
	if (NULL != pDescendant) {
		listDescendant.InsertEnd(pDescendant);
	}

	//loop the all node in listDescendant
	DWORD dwDescendantLoop = 0x00;
	AL_TreeNodeBinList<T>* pDescendantLoop = NULL;
	while (TRUE == listDescendant.Get(dwDescendantLoop, pDescendant)) {
		dwDescendantLoop++;
		if (NULL != pDescendant) {
			pDescendantLoop = pDescendant->GetChildLeft();
			if (NULL != pDescendantLoop) {
				listDescendant.InsertEnd(pDescendantLoop);
			}

			pDescendantLoop = pDescendant->GetChildRight();
			if (NULL != pDescendantLoop) {
				listDescendant.InsertEnd(pDescendantLoop);
			}
		}
		else {
			//error
			return FALSE;
		}
	}
	return TRUE;
}

/**
* Clear
*
* @param
* @return	VOID
* @note
* @attention 
*/
template<typename T> VOID 
AL_TreeNodeBinList<T>::Clear()
{
	m_dwLevel = 0x00;
	m_dwWeight = 0x00;
	m_pParent = NULL;
	m_pChildLeft = NULL;
	m_pChildRight = NULL;
}

/**
* operator () 
*
* @param	const AL_TreeNodeBinList<T>& _Left <IN>
* @param	const AL_TreeNodeBinList<T>& _Right <IN>
* @return	BOOL
* @note		Overload "()" operator, allowing the use of this class like a function. We put such a class is called a function object, 
			or called pseudo function, a function can be used as examples.
    Advantages: 
			Using the functor just like using a normal function the same, but its realization functor can access all the member 
			variables for access; rather ordinary function to communicate can only rely on global variables.
* @attention 
*/
template<typename T> BOOL 
AL_TreeNodeBinList<T>::operator () (const AL_TreeNodeBinList<T>& _Left, const AL_TreeNodeBinList<T>& _Right) const
{
	return _Left.m_dwWeight <= _Right.m_dwWeight;
}

/**
* operator () 
*
* @param	const AL_TreeNodeBinList<T>* _Left <IN>
* @param	const AL_TreeNodeBinList<T>* _Right <IN>
* @return	BOOL
* @note		Overload "()" operator, allowing the use of this class like a function. We put such a class is called a function object, 
			or called pseudo function, a function can be used as examples.
    Advantages: 
			Using the functor just like using a normal function the same, but its realization functor can access all the member 
			variables for access; rather ordinary function to communicate can only rely on global variables.
	* @attention 
*/
template<typename T> BOOL 
AL_TreeNodeBinList<T>::operator () (const AL_TreeNodeBinList<T>* _Left, const AL_TreeNodeBinList<T>* _Right) const
{
	return _Left->m_dwWeight <= _Right->m_dwWeight;
}

/**
*Assignment
*
* @param	const AL_TreeNodeBinList<T>& cAL_TreeNodeBinList
* @return	AL_TreeNodeBinList<T>&
*/
template<typename T> AL_TreeNodeBinList<T>& 
AL_TreeNodeBinList<T>::operator = (const AL_TreeNodeBinList<T>& cAL_TreeNodeBinList)
{
	m_dwLevel = cAL_TreeNodeBinList.m_dwLevel;
	m_dwWeight = cAL_TreeNodeBinList.m_dwWeight;
	m_tData = cAL_TreeNodeBinList.m_tData;
	m_pParent = cAL_TreeNodeBinList.m_pParent;
	m_pChildLeft = cAL_TreeNodeBinList.m_pChildLeft;
	m_pChildRight = cAL_TreeNodeBinList.m_pChildRight;
	return *this;
}
#endif // CXX_AL_TREENODEBINLIST_H
/* EOF */
